Objects are entities that encapsulate data and, in some environments, operations and methods associated with the object. When an object is created, a certain amount of memory is allocated for the object, and when the object is no longer needed, the memory for the object should be deallocated so that it can be reused for other purposes. In dynamic run-time environments, objects are allocated and deallocated throughout the life of program, and memory management for such dynamic objects is crucial to the correctness and performance of dynamic run-time environments.
Many dynamic run-time environments create objects that last as long as the objects are being referenced by a program, and these objects are deallocated when they are no longer referenced through a procedure known as garbage collection. There are many different kinds of garbage collectors, and experience has shown that segregating objects based on their lifetimes allows the garbage collector to employ different allocation and deallocation strategies for each set of objects.
For example, objects can be segregated into categories of newer objects (i.e. those that have been recently allocated) and older objects (i.e. those that have been less recently allocated). When an object is initially allocated, it is allocated in a memory area reserved for newer objects (“newspace”), and after a certain amount of time, the object is moved. or “tenured” into another area for older objects called “oldspace.” Because newspace tends to hold many objects that are frequently allocated and abandoned, memory allocation within this area is preferably implemented by a very fast technique such as “frontier consing” (i.e. incrementing a pointer to the beginning of free storage) and garbage collection by a copying garbage collector. On the other hand, since oldspace tends to hold fewer and longer-lived objects, it may be more desirable to perform memory allocation using a buddy or best fit allocation technique, and deallocation by a mark-sweep garbage collector.
The performance of such generational garbage collector depends on the efficiency of calculating a root set for all the objects in the newer memory area. A root set for newspace is a set of objects such that the transitive closure of objects in the set (i.e. the set of objects reachable from the object in the root set) contains all the live objects in newspace. One method of simplifying the root set calculation is to maintain a “remember table,” which is a data structure used by the garbage collector to record which objects in newspace are referenced by an object in oldspace. Accordingly, the remember table is updated when an assignment operation places a reference to a newspace object in an oldspace object. The check that occurs to determine whether the assignment operation places a reference to the newspace object in the oldspace object is referred to as a “write barrier.” It is desirable to detect and process such assignments in an efficient manner.
In run-time environments that permit multiple users to connect in separate, concurrent sessions to a server system, such as a relational database system, garbage collection poses an additional challenge. When designing a run-time environment for such a multi-user environment, scalability in terms of the number of simultaneous users who can establish separate sessions is very important. User scalability is primarily constrained by the size of the memory footprint that each session consumes. For example, a server system may have 100 Mb of memory for supporting all the user sessions. If the session memory footprint is 1 Mb, then only 100 users can be supported at one time. Therefore, it is desirable to reduce the session memory footprint to improve scalability.
One approach for reducing the session memory footprint is to provide a shorter duration memory named “call memory” that is active for the duration of a “call” but automatically deallocated when the call terminates. A call is the period of time when the user is actively using the server, such as a transaction in a database server. Accordingly, those objects that do not need to live beyond the duration of the call are placed in the call memory rather than session memory. When the call is completed, objects in the call memory are deallocated and the call-duration memory is reclaimed for us. This approach has been implemented in Oracle Corporation's PL/SQL™ language, for instance, in which objects are explicitly declared as having the duration of a call or of a session. Memory management in such a language is straightforward because the objects are simply allocated in the memory that corresponds to their duration.
The JAVA™ programming language, however, defines, the lifetime of many objects, especially system objects, to extend throughout the duration of a session and does not have the notion of a call or call memory. Accordingly, one approach is to simply ignore the provision of the call memory by the multi-user system and allocate every object in session memory, but this approach suffers from scalability because short-lived objects are unnecessarily allocated in session memory.
Another approach, however, is to allocate objects first in the shorter-duration call memory, and then, at the time the call terminates, migrate the live objects into the longer duration session memory. Dead objects, i.e. those objects that are no longer needed, are not migrated but are freed when the call memory is deallocated. In this other approach, session memory is only increased for the call memory objects that are still alive at the end of the call. One way in which call memory objects can be alive is if a live object in session memory directly or indirectly refers to the call memory object.
Additionally, it is also important to keep track of those references within session memory that refer to locations in call memory. An exit table provides a convenient mechanism for identifying which objects in call memory are still alive because they are directly or indirectly referenced by session memory objects. Accordingly, the exit table is updated when an assignment operation places a reference to a call memory object in a object living session memory, and the check that occurs to determine this happens is also referred to herein as a write barrier. Thus, it is desirable to detect and process such assignments and update the exit table efficiently.
Objects can be exhibit many different lifetimes, and these lifetimes need not be comparable. Accordingly, maintenance of remember tables (or exit tables) grows in complexity, in that management of the variety of lifetimes is unwieldy. Consequently, garbage collection becomes inefficient under such circumstances. It is noted that various objects may require different out-of-line handling. That is, depending on the data structure that is utilized to record which objects in newspace are referenced by an object in oldspace, multiple out-of-line routines can be employed to execute update of the corresponding data structure. Performance, thus, is governed by how quickly the corresponding routine is dispatched.
Therefore, a need exists for distinguishing relative object lifetimes at assignment time to improve efficiency of garbage collection. There is also a need for rapidly invoking the proper routine to update a data structure such as an exit table or a remember table in support of garbage collection.